/* 畜栏保留问题 */

#include<iostream>
#include<algorithm>
using namespace std;

struct TCow
{
	int start;
	int end;
	int idx;

	TCow(int s, int e) 
	: start(s)
	, end(e)
	, idx(-1)
 	{
	}		
};

struct CompCow
{
	bool operator()(const TCow &lhs, const TCow &rhs)
	{
		return lhs.start < rhs.start;
	}
};

int main(void)
{
	constexpr int N = 5;
	TCow cows[N] = {
		TCow(1, 10),
		TCow(2, 4),
		TCow(3, 6),
		TCow(5, 8),
		TCow(4, 7)
	};

	sort(cows, cows + N, CompCow{});
	
	int nCorral = 1;

	int nEarlistEnd = cows[0].end;
	int nEarlistIdx = 0;
	int endTime[N]{nEarlistEnd, 0};

	cows[0].idx = 1;
	for (int i = 1; i < N; i++)
	{
		/* 如果第i头牛的起始时间，比最早的结束时间还早，要加一个畜栏*/
		if (cows[i].start < nEarlistEnd)
		{
			endTime[nCorral] = cows[i].end;
			nCorral++;
			cows[i].idx = nCorral;
		}
		else
		{
			/* 第i头牛接着使用第nEarlistIdx个畜栏即可 */
			cows[i].idx = nEarlistIdx + 1;	//畜栏的编号是从1开始的，比数组下标大1
			endTime[nEarlistIdx] = cows[i].end;
			nEarlistEnd = cows[i].end;
		}

		/* 更新最短结束时间 */
		for (int i = 0; i < nCorral; i++)
		{
			if (endTime[i] < nEarlistEnd)
			{
				nEarlistEnd = endTime[i];
				nEarlistIdx = i;
			}
		}
	}

	cout<< "we need " << nCorral << " corrals\n";
	for_each(cows, cows + N, [](auto e){cout<< e.idx << " ";});
	cout<< "\n";
}

